package top.ivansong92.example.leetcode.learning.data.struct.linklist;


import org.junit.Test;

import java.util.*;

public class TestExample1 {
    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {}
        ListNode(int x) {
            val = x;
        }

        public static ListNode attrToListNode(int[] attr) {
           if (attr == null || attr.length == 0) {
               return null;
           }
           ListNode head = new ListNode(attr[0]);
           ListNode cur = head;
           for(int i = 1; i < attr.length; i ++) {
               cur.next = new ListNode(attr[i]);
               cur = cur.next;
           }
           return head;
        }

        @Override
        public String toString() {
            StringBuffer stringBu = new StringBuffer();
            stringBu.append("[");
            ListNode cur = this;
            while (cur != null) {
                stringBu.append(cur + "->");
                cur = cur.next;
            }
            stringBu.append("null]");
            return stringBu.toString();
        }
    }

    /**
     * 83. 删除排序链表中的重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = head, nextNode;
        int currentVal, nextVal;
        while (node != null) {
            currentVal = node.val;
            nextNode = node.next;
            if (nextNode == null) {
                break;
            }

            nextVal = nextNode.val;
            if (currentVal == nextVal) {
                node.next = nextNode.next;
                nextNode.next = null;
            } else {
                node = node.next;
            }
        }
        return head;
    }

    /**
     * 143. 重排链表
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        List<ListNode> nodeList = new ArrayList<>();
        ListNode index = head;
        while (index != null) {
            nodeList.add(index);
            index = index.next;
        }

        int i = 1, j = nodeList.size() - 1;
        boolean back = true;
        index = head;
        while (i <= j) {
            ListNode node;
            if (back) {
                node = nodeList.get(j);
                j --;
                back = false;
            } else {
                node = nodeList.get(i);
                i ++;
                back = true;
            }
            index.next = node;
            node.next = null;
            index = index.next;
        }
    }

    @Test
    public void testSpiralOrder() {
        System.out.println(deleteDuplicatesV2(ListNode.attrToListNode(new int[]{1,2,2})));
    }

    /**
     * 82. 删除排序链表中的重复元素 II
     * @param head
     * @return
     */
    public ListNode deleteDuplicatesV2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmp = new ListNode(0);
        tmp.next = head;
        ListNode pre = tmp , current = head;
        while (current != null && current.next != null) {
            int currentVal = current.val;
            int nextVal = current.next.val;
            if (currentVal == nextVal) {
                while (current != null && current.val == currentVal) {
                    current = current.next;
                }
                pre.next = current;
            } else {
                pre = current;
                current = current.next;
            }
        }
        return tmp.next;
    }
}
